package arithmetic;

/**
 * @author Ajie
 * @date 2024/4/13
 * @function 并查集
 */
public class UnionQuick {
    private final int[] parentNode;//有 n 个 root ,依次都合并。。。根据相关性
    private final int[] rank;//根结点的 rank ,一般指，深度。 虽然这个 不准确 而且会变。 查看 UnionFindDynamic
    //parentNode 数组，表示，所有的元素。
    // parentNode[i]-->val 表示 他爹 是 谁。 eg:1 的 爹是谁：  parentNode[1] = 1  or 2 。。。
    private int count;

    //init
    public UnionQuick(int n) {
        this.parentNode = new int[n];
        this.rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parentNode[i] = i;// 自己的 -- 父节点 --自己。
//            rank[i]=0;def is 0
        }
    }

    //根节点。。 parentNode[k] = k .始祖，自己就是爹。
    public int findRoot(int i) {
        int tempRoot = i;
        //找到 root  tempRoot
        while (tempRoot != parentNode[tempRoot]) {//他爹，不是自己。。继续
            //找到了 他爹，
            tempRoot = parentNode[tempRoot];//继续找， tempRoot爹。
        }
        //路径压缩，
        // only 压缩 i 指向-->root
//        if (tempRoot != i) {
//            parentNode[i] = tempRoot;
//        }
        //压缩，所有的节点。这条线上的。。子节点
        while (i != tempRoot) {
            int tempP = parentNode[i];
            parentNode[i] = tempRoot;//所有的节点---》root.
            i = tempP;
        }
        return tempRoot;
    }

    public void union(int p, int q) {
//                int proot = parentNode[p];
//                int qroot = parentNode[q];
        int proot = findRoot(p);
        int qroot = findRoot(q);
        if (proot != qroot) {
            if (rank[proot] > rank[qroot]) {
                parentNode[qroot] = proot;
            } else if (rank[proot] < rank[qroot]) {
                parentNode[proot] = qroot;
            } else {
                parentNode[proot] = qroot;
                rank[qroot] += 1;
            }
            count--;//不需要单独统计了。
        }
    }

    public int rootCount() {
//                int count = 0;
//                for (int i = 0; i < parentNode.length; i++) {
//                    if (parentNode[i] == i) {
//                        count++;
//                    }
//                }
        return count;
    }
}